package datastructure.sort;

/**
 * @author yinlei
 * @date 2018/7/2
 * @since 1.0.0
 */
public class InsertionSort implements SortMain.Sort {

    public void sort(int[] a) {

        int n = a.length;

        // 插入排序，是移动位置，非交换位置
        for (int i = 1; i < n; i++) {
            int pos = i;
            int val = a[i];
            for (int j = i - 1; j > -1; j--) {
                if (val < a[j]) {
                    a[j + 1] = a[j];
                    pos = j;
                } else {
                    break;
                }
            }
            a[pos] = val;
        }
    }
}
